package com.huangyi;

public class Main {
    public static void main(String[] args) {
       //只出现一次的数字
        class Solution {
            public int singleNumber(int[] nums) {
                int ret = 0;
                // 遍历数组，逐个异或
                for (int num : nums) {
                    ret ^= num;
                }
                return ret;
            }
        }

        //只出现一次的数字III
        class Solution2 {
            public int[] singleNumber(int[] nums) {
                // 第一步：全体异或，得到 a ^ b
                int tmp = 0;
                for (int num : nums) {
                    tmp ^= num;
                }

                // 第二步：取最低位的 1 作为区分标志
                int mark = Integer.lowestOneBit(tmp);

                // 第三步：分组异或
                int a = 0, b = 0;
                for (int num : nums) {
                    if ((num & mark) == 0) {
                        a ^= num;
                    } else {
                        b ^= num;
                    }
                }
                return new int[]{a, b};
            }
        }
    }
}